`:top
In `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, and more precisely regarding `F33f`_`[data structures`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_structure]`_`f, a `!persistent array`! is a `F33f`_`[persistent data structure`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Persistent_data_structure]`_`f with properties similar to a (non-persistent) `F33f`_`[array`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Array_data_structure]`_`f. That is, after a value's update in a persistent array, there exist two persistent arrays: one persistent array in which the update is taken into account, and one which is equal to the array before the update.
>>Contents
• `F0af`_`[Difference between persistent arrays and arrays`#difference-between-persistent-arrays-and-arrays]`_`f
• `F0af`_`[Lower Bound on Persistent Array Lookup Time`#lower-bound-on-persistent-array-lookup-time]`_`f
• `F0af`_`[Implementations`#implementations]`_`f
• `F0af`_`[Worst case log-time`#worst-case-log-time]`_`f
• `F0af`_`[Shallow binding`#shallow-binding]`_`f
• `F0af`_`[Expected amortized log-log-time`#expected-amortized-log-log-time]`_`f
• `F0af`_`[Worst case log-log-time`#worst-case-log-log-time]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Difference between persistent arrays and arrays
An array a r = [ e 0 , … … , e n − − 1 ] {\\displaystyle \\mathrm {ar} =[e_{0},\\dots ,e_{n-1}]} is a data structure, with a fixed number `*n`* of elements e 0 , … … , e n − − 1 {\\displaystyle e_{0},\\dots ,e_{n-1}} . It is expected that, given the array `*ar`* and an index 0 ≤ ≤ i < n {\\displaystyle 0\\leq i<n} , the value e i {\\displaystyle e_{i}} can be retrieved quickly. This operation is called a `!lookup`!. Furthermore, given the array `*ar`*, an index 0 ≤ ≤ i < n {\\displaystyle 0\\leq i<n} and a new value `*v`*, a new array `*ar2`* with content [ e 0 , … … , e i − − 1 , v , e i + 1 , … … , e n − − 1 ] {\\displaystyle [e_{0},\\dots ,e_{i-1},v,e_{i+1},\\dots ,e_{n-1}]} can be created quickly. This operation is called an `!update`!. The main difference between persistent and non-persistent arrays being that, in non-persistent arrays, the array `*ar`* is destroyed during the creation of `*ar2`*.
For example, consider the following pseudocode.
`B100`F9d9array = [0, 0, 0]`f`b
`B100`F9d9updated_array = array.update(0, 8)`f`b
`B100`F9d9other_array = array.update(1, 3)`f`b
`B100`F9d9last_array = updated_array.update(2, 5)`f`b
At the end of execution, the value of `*array`* is still [0, 0, 0], the value of `*updated_array`* is [8, 0, 0], the value of `*other_array`* is [0, 3, 0], and the value of `*last_array`* is [8, 0, 5].
There exist two kinds of persistent arrays. A persistent array may be either `!partially`! or `!fully`! persistent. A fully persistent array may be updated an arbitrary number of times while a partially persistent array may be updated at most once. In our previous example, if `*array`* were only partially persistent, the creation of `*other_array`* would be forbidden; however, the creation of `*last_array`* would still be valid. Indeed, `*updated_array`* is an array distinct from `*array`* and has never been updated before the creation of `*last_array`*.
>>Lower Bound on Persistent Array Lookup Time
Given that non-persistent arrays support both updates and lookups in constant time, it is natural to ask whether the same is possible with persistent arrays. The following theorem shows that under mild assumptions about the space complexity of the array, lookups must take Ω Ω ( log log n ) {\\displaystyle \\Omega (\\log \\log n)} time in the worst case, regardless of update time, in the `F33f`_`[cell-probe model`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cell-probe_model]`_`f.
`!Theorem`:cite-ref-straka-1-0[`F5bf`_`[1`#cite-note-straka-1]`_`f]`!—Consider a partially persistent array with n {\\displaystyle n} elements and m = n γ γ {\\displaystyle m=n^{\\gamma }} modifications, where γ γ {\\displaystyle \\gamma } is a constant fulfilling 1 < γ γ ≤ ≤ 2 {\\displaystyle 1<\\gamma \\leq 2} . Assuming the space complexity of the array is O ( m log k m ) {\\displaystyle O(m\\log ^{k}m)} for a constant k {\\displaystyle k} , the lower bound on the lookup complexity in this partially persistent array is Ω Ω ( log log n ) {\\displaystyle \\Omega (\\log \\log n)} .
>>Implementations
In this section, n {\\displaystyle n} is the number of elements of the array, and m {\\displaystyle m} is the number of updates.
>>>Worst case log-time
The most straightforward implementation of a fully persistent array uses an arbitrary persistent map, whose keys are the numbers from `*0`* to `*n`* − 1. A persistent map may be implemented using a persistent `F33f`_`[balanced tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Balanced_tree]`_`f, in which case both updates and lookups would take O ( log n ) {\\displaystyle O(\\log n)} time. This implementation is optimal for the `F33f`_`[pointer machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Pointer_machine]`_`f model.`:cite-ref-straka-1-1[`F5bf`_`[1`#cite-note-straka-1]`_`f]
>>>Shallow binding
A fully persistent array may be implemented using an array and the so-called Baker's trick.`:cite-ref-ml-2-0[`F5bf`_`[2`#cite-note-ml-2]`_`f] This implementation is used in the `F33f`_`[OCaml`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=OCaml]`_`f module parray.ml`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f] by Jean-Christophe Filliâtre.
In order to define this implementation, a few other definitions must be given. An `!initial array`! is an array that is not generated by an update on another array. A `!child`! of an array `*ar`* is an array of the form `*ar.update(i,v)`*, and `*ar`* is the `!parent`! of `*ar.update(i,v)`*. A `!descendant`! of an array `*ar`* is either `*ar`* or the descendant of a child of `*ar`*. The `!initial array`! of an array `*ar`* is either `*ar`* if `*ar`* is initial, or it is the initial array of the parent of `*ar`*. That is, the initial array of `*ar`* is the unique array `*init`* such that a r = i n i t . u p d a t e ( i 0 , v 0 ) . … … . u p d a t e ( i m , v m ) {\\displaystyle \\mathrm {ar} =init.update(i_{0},v_{0}).\\dots .update(i_{m},v_{m})} , with `*init`* initial and i 0 , … … , i m {\\displaystyle i_{0},\\dots ,i_{m}} an arbitrary sequence of indexes and v 0 , … … , v m {\\displaystyle v_{0},\\dots ,v_{m}} an arbitrary sequence of value. A `*family`* of arrays is thus a set of arrays containing an initial array and all of its descendants. Finally, the tree of a family of arrays is the `F33f`_`[tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Tree_(data_structure)]`_`f whose nodes are the arrays, and with an edge `*e`* from `*ar`* to each of its children `*ar.update(i,v)`*.
A persistent array using Baker's trick consists of a pair with an actual array called `*array`* and the tree of arrays. This tree admits an arbitrary root - not necessarily the initial array. The root may be moved to an arbitrary node of the tree. Changing the root from `*root`* to an arbitrary node `*ar`* takes time proportional to the depth of `*ar`*. That is, in the distance between `*root`* and `*ar`*. Similarly, looking up a value takes time proportional to the distance between the array and the root of its family. Thus, if the same array `*ar`* may be lookup multiple times, it is more efficient to move the root to `*ar`* before doing the lookup. Finally updating an array only takes `F33f`_`[constant time`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Constant_time]`_`f.
Technically, given two adjacent arrays `*ar1`* and `*ar2`*, with `*ar1`* closer to the root than `*ar2`*, the edge from `*ar1`* to `*ar2`* is labelled by `*(i,ar2[i])`*, where `*i`* the only position whose value differ between `*ar1`* and `*ar2`*.
Accessing an element `*i`* of an array `*ar`* is done as follows. If `*ar`* is the root, then `*ar[i]`* equals `*root[i]`*. Otherwise, let `*e`* the edge leaving `*ar`* toward the root. If the label of `*e`* is `*(i,v)`* then `*ar[i]`* equals `*v`*. Otherwise, let `*ar2`* be the other node of the edge `*e`*. Then `*ar[i]`* equals `*ar2[i]`*. The computation of `*ar2[i]`* is done recursively using the same definition.
The creation of `*ar.update(i,v)`* consists in adding a new node `*ar2`* to the tree, and an edge `*e`* from `*ar`* to `*ar2`* labelled by `*(i,v)`*.
Finally, moving the root to a node `*ar`* is done as follows. If `*ar`* is already the root, there is nothing to do. Otherwise, let `*e`* the edge leaving `*ar`* toward the current root, `*(i,v)`* its label and `*ar2`* the other end of `*e`*. Moving the root to `*ar`* is done by first moving the root to `*ar2`*, changing the label of `*e`* to `*(i, ar2[i])`*, and changing `*array[i]`* to `*v`*.
Updates take O ( 1 ) {\\displaystyle O(1)} time. Lookups take O ( 1 ) {\\displaystyle O(1)} time if the root is the array being looked up, but Θ Θ ( m ) {\\displaystyle \\Theta (m)} time in the worst case.
>>>Expected amortized log-log-time
In 1989, Dietz`:cite-ref-dietz-4-0[`F5bf`_`[4`#cite-note-dietz-4]`_`f] gave an implementation of fully persistent arrays using O ( m + n ) {\\displaystyle O(m+n)} space such that lookups can be done in O ( log log m ) {\\displaystyle O(\\log \\log m)} worst-case time, and updates can be done in O ( log log m ) {\\displaystyle O(\\log \\log m)} expected amortized time. By the lower bound from the previous section, this time complexity for lookup is optimal when m = n γ γ {\\displaystyle m=n^{\\gamma }} for γ γ ∈ ∈ ( 1 , 2 ] {\\displaystyle \\gamma \\in (1,2]} . This implementation is related to the `F33f`_`[order-maintenance problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Order-maintenance_problem]`_`f and involves `F33f`_`[vEB trees`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=VEB_tree]`_`f, one for the entire array and one for each index.
Straka showed that the times for both operations can be (slightly) improved to O ( log log min ( m , n ) ) {\\displaystyle O(\\log \\log \\min(m,n))} .`:cite-ref-straka-1-2[`F5bf`_`[1`#cite-note-straka-1]`_`f]
>>>Worst case log-log-time
Straka showed how to achieve O ( ( log log m ) 2 / log log log m ) {\\displaystyle O((\\log \\log m)^{2}/\\log \\log \\log m)} worst-case time and linear ( O ( m + n ) {\\displaystyle O(m+n)} ) space, or O ( log log m ) {\\displaystyle O(\\log \\log m)} worst-case time and super-linear space. It remains open whether it is possible to achieve worst-case time O ( log log m ) {\\displaystyle O(\\log \\log m)} subject to linear space.`:cite-ref-straka-1-3[`F5bf`_`[1`#cite-note-straka-1]`_`f]
>>References
`:cite-note-straka-1`!1.`! `F0af`_`[↑`#cite-ref-straka-1-0]`_`f `:citerefstraka-e2013`aStraka e, Milan (2013). `*Functional Data Structures and Algorithms`*. Prague.`B100`F9d9{{cite book}}`f`b: CS1 maint: location missing publisher (link)
`:cite-note-ml-2`!2.`! `F0af`_`[↑`#cite-ref-ml-2-0]`_`f `:citereffill-treconchon2007`aFillâtre, Jean-Christophe; Conchon, Sylvain (2007). `*A Persistent Union-find Data Structure`* (PDF). New York, NY, USA: ACM. pp. 37–46. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1-59593-676-9.
`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citereffilli-tre`aFilliâtre, Jean-Christophe. "Persistent-array implementation". `*`F33f`_`[GitHub`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=GitHub]`_`f`*.
`:cite-note-dietz-4`!4.`! `F0af`_`[↑`#cite-ref-dietz-4-0]`_`f `:citerefdietz1989`aDietz, Paul F. (1989). "Fully persistent arrays". `*Proceedings of the Algorithms and Data Structures`*. pp. 67–74. `F33f`_`[CiteSeerX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CiteSeerX_(identifier)]`_`f 10.1.1.621.1599. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/3-540-51542-9_8.
.
`c`F0af`_`[↑ Back to top`#top]`_`f`a